external hash_param : int -> int -> 'a -> int = "caml_hash_univ_param" "noalloc";

value hash x = hash_param 10 100 x;
(* We do dynamic hashing, and resize the table and rehash the elements
   when buckets become too long. *)
type bucketlist 'a = [ Empty | Cons of 'a and bucketlist 'a ] 
and t 'a =
  { size : mutable int; (* number of elements *)
    data : mutable array (bucketlist 'a)
  };

value create initial_size =
  let s = min (max 1 initial_size) Sys.max_array_length
  in { size = 0; data = Array.make s Empty; };

value empty () = {size = 0; data = Array.make 1 Empty };

value clear h =
(
  for i = 0 to (Array.length h.data) - 1 do h.data.(i) := Empty done;
  h.size := 0
);

value copy h = { size = h.size; data = Array.copy h.data; };
value length h = h.size;
value is_empty h = h.size = 0;

value resize hashfun tbl =
  let odata = tbl.data in
  let osize = Array.length odata in
  let nsize = min ((2 * osize) + 1) Sys.max_array_length
  in
    if nsize <> osize
    then
      let ndata = Array.create nsize Empty in
      let rec insert_bucket = fun
        [ Empty -> ()
        | Cons data rest ->
          (
            insert_bucket rest;(* preserve original order of elements *)
            let nidx = (hashfun data) mod nsize;
            Array.unsafe_set ndata nidx (Cons data ndata.(nidx))
          ) 
        ]

      in
      (
        for i = 0 to osize - 1 do 
          insert_bucket (Array.unsafe_get odata i) 
        done;
        tbl.data := ndata
      )
    else ();

value add h data =
  let i = (hash data) mod (Array.length h.data) in
  let rec mem_in_bucket = fun
    [ Empty -> False
    | Cons d rest -> (d = data) || (mem_in_bucket rest) 
    ]
  in
  let b = Array.unsafe_get h.data i in
  if b = Empty || not (mem_in_bucket b)
  then
    let bucket = Cons data b in
    (
      Array.unsafe_set h.data i bucket;
      h.size := succ h.size;
      if h.size > ((Array.length h.data) lsl 1) then resize hash h else ()
    )
  else ();

value singleton v = { size = 1; data = [| Cons v Empty |] };

value remove h data =
  let rec remove_bucket = fun
    [ Empty -> Empty
    | Cons d next ->
        if d = data
        then (h.size := pred h.size; next)
        else Cons d (remove_bucket next) 
    ] 
  in
  let i = (hash data) mod (Array.length h.data) in 
  Array.unsafe_set h.data i (remove_bucket (Array.unsafe_get h.data i));

value remove_exn h data = 
  let rec remove_bucket = fun
    [ Empty -> raise Not_found
    | Cons d next ->
        if d = data
        then (h.size := pred h.size; next)
        else Cons d (remove_bucket next) 
    ] 
  in
  let i = (hash data) mod (Array.length h.data) in 
  Array.unsafe_set h.data i (remove_bucket (Array.unsafe_get h.data i));

value mem h data =
  match Array.unsafe_get h.data ((hash data) mod (Array.length h.data)) with
  [ Empty -> False
  | Cons d rest -> 
    let rec mem_in_bucket = fun
      [ Empty -> False
      | Cons d rest -> (d = data) || (mem_in_bucket rest) 
      ]
    in
    (d = data) || (mem_in_bucket rest)
  ];

value iter f h =
  let rec do_bucket = fun 
    [ Empty -> () 
    | Cons d rest -> (f d; do_bucket rest) 
    ] 
  in
  let d = h.data in 
  for i = 0 to (Array.length d) - 1 do 
    do_bucket d.(i) 
  done;

value fold f h init =
  let rec do_bucket b accu =
    match b with
    [ Empty -> accu
    | Cons d rest -> do_bucket rest (f d accu) ] in
  let d = h.data in
  let accu = ref init
  in
  (
    for i = 0 to (Array.length d) - 1 do
      accu.val := do_bucket d.(i) accu.val
    done;
    accu.val
  );


value to_list t = fold (fun e l -> [ e :: l ] ) t [];
